package 剑指offer;

import java.util.LinkedList;

/**
 * A2
 */
public class A2 {

    public String addBinary(String a, String b) {
        char[] as=a.toCharArray(),bs=b.toCharArray();
        LinkedList<Character> a_LinkedList=new LinkedList<>(),b_LinkedList=new LinkedList<>();
        for (Character character : as) {
            a_LinkedList.add(character);
        }
        for (Character character : bs) {
            b_LinkedList.add(character);
        }
        StringBuilder stringBuilder=new StringBuilder();
        int flag=0;
        while (!a_LinkedList.isEmpty()||!b_LinkedList.isEmpty()) {
            Character aCharacter='0';
            if (!a_LinkedList.isEmpty()) {
                aCharacter=a_LinkedList.pollLast();
            }
            
            Character bCharacter='0';
            if (!b_LinkedList.isEmpty()) {
               bCharacter=b_LinkedList.pollLast();
            }
            if (aCharacter=='1') {
                flag+=1;
            }
            if (bCharacter=='1') {
                flag+=1;
            }
            if (flag%2==0) {
                stringBuilder.append('0');
            }else{
                stringBuilder.append('1');
            }
            flag/=2;
        }
        if (flag!=0) {
            stringBuilder.append('1');
        }
        
        return stringBuilder.reverse().toString();
    }
}